#include <iostream>

const int capacity = 10;

template<typename T>
class MaxHeap
{
public:

    MaxHeap():size(0){}

    void Insert(T value)
    {
        array[size] = value;
        SiftUp(size);
        size++;
    }
    
    void RemoveRoot()//删除根
    {
        if(size == 0)
            return;
        array[0] = array[--size]; //让根的值等于数组最后面的那个值,size - 1
        // array[0] = array[size - 1];
        // size--;
        SiftDown(0); //把当前的根下沉
    }

    void show()
    {
        for(int i = 0; i < size; i++)
        {
            std::cout<<array[i]<<" ";
        }
        std::cout<<std::endl;
    }

private:
    int GetParent(T i){return (i - 1) / 2;}//获取双亲节点下标
    int GetLeftChild(T i){return 2 * i + 1;}//获取左孩子节点下标
    int GetRightChild(T i){return 2 * i + 2;}//获取右孩子节点下标

    void SiftUp(T i)
    {
        while(array[i] > array[GetParent(i)] && i > 0) //判断条件
        {
            std::swap(array[i],array[GetParent(i)]); //交换当前节点与双亲节点
            i = GetParent(i); //让当前节点的下标等于其双亲节点的下标
        }
    }

    void SiftDown(T i)
    {
        int LeftChild = GetLeftChild(i);
        int RightChild = GetRightChild(i);

        int Max = i; 
        //左孩子存在且值比我大
        if(LeftChild < size && array[LeftChild] > array[i])
        {
            Max = LeftChild;
        }
        //右孩子也存在且比我和左孩子的值都大
        if(RightChild < size && array[RightChild] > array[Max])
        {
            Max = RightChild;
        }
        //最大值不是我
        if(Max != i)
        {
            std::swap(array[i],array[Max]);
            SiftDown(Max);
        }
    }

    T array[capacity]; //数组
    int size; // 当前数组元素个数
};


